蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Word Break Word Break II 单词拆分 单词拆分 II

发表于 更新于 分类于 阅读次数： Valine：

Word Break

题目大意

给定一个目标字符串和一组字符串，判断目标字符串能否拆分成数个字符串，这些字符串都在给定的那组字符串中。

解题思路

动态规划

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(n):
            for j in range(i, -1, -1):
                print j, i, s[j:i + 1], dp
                if dp[j] and s[j:i + 1] in wordDict:
                    dp[i + 1] = True
                    break
            print '-----loop-----'
        return dp[n]

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
0 0 l [True, False, False, False, False, False, False, False, False]
-----loop-----
1 1 e [True, False, False, False, False, False, False, False, False]
0 1 le [True, False, False, False, False, False, False, False, False]
-----loop-----
2 2 e [True, False, False, False, False, False, False, False, False]
1 2 ee [True, False, False, False, False, False, False, False, False]
0 2 lee [True, False, False, False, False, False, False, False, False]
-----loop-----
3 3 t [True, False, False, False, False, False, False, False, False]
2 3 et [True, False, False, False, False, False, False, False, False]
1 3 eet [True, False, False, False, False, False, False, False, False]
0 3 leet [True, False, False, False, False, False, False, False, False]
-----loop-----
4 4 c [True, False, False, False, True, False, False, False, False]
3 4 tc [True, False, False, False, True, False, False, False, False]
2 4 etc [True, False, False, False, True, False, False, False, False]
1 4 eetc [True, False, False, False, True, False, False, False, False]
0 4 leetc [True, False, False, False, True, False, False, False, False]
-----loop-----
5 5 o [True, False, False, False, True, False, False, False, False]
4 5 co [True, False, False, False, True, False, False, False, False]
3 5 tco [True, False, False, False, True, False, False, False, False]
2 5 etco [True, False, False, False, True, False, False, False, False]
1 5 eetco [True, False, False, False, True, False, False, False, False]
0 5 leetco [True, False, False, False, True, False, False, False, False]
-----loop-----
6 6 d [True, False, False, False, True, False, False, False, False]
5 6 od [True, False, False, False, True, False, False, False, False]
4 6 cod [True, False, False, False, True, False, False, False, False]
3 6 tcod [True, False, False, False, True, False, False, False, False]
2 6 etcod [True, False, False, False, True, False, False, False, False]
1 6 eetcod [True, False, False, False, True, False, False, False, False]
0 6 leetcod [True, False, False, False, True, False, False, False, False]
-----loop-----
7 7 e [True, False, False, False, True, False, False, False, False]
6 7 de [True, False, False, False, True, False, False, False, False]
5 7 ode [True, False, False, False, True, False, False, False, False]
4 7 code [True, False, False, False, True, False, False, False, False]
-----loop-----

可以看到，把dp[0]设置为True是一个分割，每一个true都是一个分割点。

Word Break II

题目大意

给定一个目标字符串和一组单词，将目标字符串进行拆分，要求拆分出的部分在那个单词组中，拆分后的单词用空格隔开，给出所有可能的拆分情况。

解题思路

动态规划+深度优先
参考：http://www.cnblogs.com/zuoyuan/p/3760804.html
这道题不只像word break那样判断是否可以分割，而且要找到所有的分割方式，那么我们就要考虑dfs了。

不过直接用dfs解题是不行的，为什么？因为决策树太大，如果全部遍历一遍，时间复杂度太高，无法通过oj。

那么我们需要剪枝，如何来剪枝呢？使用word break题中的动态规划的结果，在dfs之前，先判定字符串是否可以被分割，如果不能被分割，直接跳过这一枝。实际上这道题是dp+dfs。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        Solution.res = []
        self.dfs(s, wordDict, '')
        return Solution.res
        
    def dfs(self, s, wordDict, stringlist):
        if self.check(s, wordDict):
            # 如果s已经切完，则加入最后结果集
            if len(s) == 0: 
                Solution.res.append(stringlist[1:])
            for i in range(1, len(s)+1):
                if s[:i] in wordDict:
                    print stringlist+' '+s[:i]
                    self.dfs(s[i:], wordDict, stringlist+' '+s[:i])
    
    def check(self, s, wordDict):
            dp = [False for i in range(len(s)+1)]
            dp[0] = True
            # 这里循环是len(s)，使得该check函数变成了只要有单词在里面就验证成功，和wordbreak有所不同！
            for i in range(len(s)):
                for j in range(i, -1, -1):
                    if dp[j] and s[j:i + 1] in wordDict:
                        dp[i + 1] = True
                        break
            return dp[len(s)]

输出：

1
2
3
4
5
6
cat
cat sand
cat sand dog
cats
cats and
cats and dog

总结